package leetcode;

import java.util.*;

/**
 * 三数之和为0
 * 15th 中等
 * https://leetcode-cn.com/problems/3sum/description/
 */
public class ThreeSum {

    public static void main(String[] args) {
        int[] nums = {0, 0, 0, 0};
        new ThreeSum().threeSum(nums);
    }

    public List<List<Integer>> threeSum(int[] nums){
        Arrays.sort(nums);
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = null;
        for(int i = 0; i < len - 2; i++){
            if(nums[i] > 0){
                break;
            }
            for(int j = i + 1; j < len - 1; j++){
                int sum2 = nums[i] + nums[j];
                if(sum2 > 0){
                    break;
                }
                if(list != null){
                    if(list.get(0) == nums[i]
                            && list.get(1) == nums[j]){
                        continue;
                    }
                }
                if(sum2 + nums[len - 1] < 0){
                    continue;
                }
                for(int k = j + 1; k < len; k++){
                    if(list != null){
                        if(list.get(0) == nums[i]
                                && list.get(1) == nums[j]
                                && list.get(2) == nums[k]){
                            continue;
                        }
                    }
                    int sum = sum2 + nums[k];
                    if(sum == 0){
                        list= new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        /*boolean flag = true;
                        for(List<Integer> item: res){
                            if(item.get(0) == list.get(0)
                                    && item.get(1) == list.get(1)
                                    && item.get(2) == list.get(2)){
                                flag = false;
                                break;
                            }
                        }
                        if(flag){
                        }*/
                        res.add(list);
                    }else if(sum > 0){
                        break;
                    }
                }
            }
        }
        return res;
    }
}
